package DFS_BFS;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @PackageName: DFS_BFS
 * @ClassName: Leetcode127
 * @Author: chen jinxu
 * @Date: 2022/2/27 10:11
 *  字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
 * 每一对相邻的单词只差一个字母。
 *  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * 输出：5
 * 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
 *
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。
 
 */
public class Leetcode127 {
    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = new ArrayList<>();
        wordList.add("hot");
        wordList.add("dot");
        wordList.add("dog");
        wordList.add("lot");
        wordList.add("log");
        wordList.add("cog");
        int result = ladderLength(beginWord, endWord, wordList);
        System.out.println(result);
    }

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // bfs 队列
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        // bfs需要一个标记，标记处理过的点
        boolean[] marked = new boolean[wordList.size() + 1];
        // 定义返回值
        int layer = 1;
        while (!queue.isEmpty()) {  // 记录层数
            layer++;
            int size = queue.size();
            while (size-- > 0) {
                String cur = queue.poll();
                for (int i = 0; i < wordList.size(); i++) {
                    if (marked[i]) {
                        continue;
                    }
                    String dic = wordList.get(i);
                    if (canChanange(cur, dic)) {
                        if (dic.equals(endWord)) {
                            return layer;
                        }
                     queue.add(dic);
                        marked[i] = true;
                    }
                }
            }
        }
        return 0;
    }

    private static boolean canChanange(String cur, String dic) {
        int diff = 0;
        for (int i = 0; i < dic.length(); i++) {
            if (cur.charAt(i) != dic.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }
}
